﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BoardAlgorithm
{
    public class BoardPoint
    {
        public int X { get; protected set; }
        public int Y { get; protected set; }
        public BoardPoint(int x, int y)
        {
            X = x;
            Y = y;
        }
        public override bool Equals(object obj)
        {
            BoardPoint tmp = obj as BoardPoint;
            if (tmp == null)
            {
                return false;
            }

            return tmp.X == this.X
                && tmp.Y == this.Y;
        }

        public override string ToString()
        {
            return string.Format("{0}:{1}", X, Y);
        }

        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
    }
    public class Board
    {
        #region Fields
        private int _rowCount;
        private int _colCount;

        private int _yStart = 0;

        private BoardBlock[,] _chessBoard;
        #endregion

        /// <summary>
        /// Chess board
        /// </summary>
        /// <param name="width"></param>
        /// <param name="height"></param>
        public Board(int rowCount, int colCount
            , BoardPoint startPosLeft, BoardPoint startPosRight
            , BoardPoint endPosLeft, BoardPoint endPosRight
            , BoardPoint[] blockes)
        {
            _rowCount = rowCount;
            _colCount = colCount;
            _chessBoard = new BoardBlock[_rowCount, _colCount];



            ResetChessBoard(startPosLeft, startPosRight, endPosLeft, endPosRight, blockes);
            
        }

        private void ResetChessBoard(BoardPoint startPosLeft, BoardPoint startPosRight
            , BoardPoint endPosLeft, BoardPoint endPosRight, BoardPoint[] blocks)
        {
            // set start pos
            _yStart = startPosLeft.Y;


            for (int y = 0; y != _rowCount; ++y)
            {
                for (int x = 0; x != _colCount; ++x)
                {
                    _chessBoard[y, x] = new BoardBlock(x, y);
                }
            }

            // set block
            if (blocks != null)
            {
                foreach (BoardPoint p in blocks)
                {
                    try
                    {

                        _chessBoard[p.Y, p.X].Status = BlockStatus.Blocked;
                    }
                    catch (Exception e)
                    {
                        Console.Write(e);
                    }
                }
            }

            bool fs1 = true, fs2 = true, fe1 = true, fe2 = true;
            #region Check there's cover
            if (endPosLeft.Equals(startPosLeft))
            {
                fe1 = false; fs1 = false;
            }
            if (endPosLeft.Equals(startPosRight))
            {
                fe1 = false; fs2 = false;
            }

            if (endPosRight.Equals(startPosLeft))
            {
                fe2 = false; fs1 = false;
            }
            if (endPosRight.Equals(startPosRight))
            {
                fe2 = false; fs2 = false;
            }
            #endregion

            #region Set Start Pos & End Position
            if ((fs1 == false && fs2 == false)
                || (fe1 == false && fe2 == false))
            {
                // set start
                _chessBoard[startPosLeft.Y, startPosLeft.X].Status = BlockStatus.StartGot;
                _chessBoard[startPosLeft.Y, startPosLeft.X].TurnCount = 0;
                _chessBoard[startPosLeft.Y, startPosLeft.X].IsStart = true;

                

                // set end
                _chessBoard[endPosRight.Y, endPosRight.X].Status = BlockStatus.EndGot;
                _chessBoard[endPosRight.Y, endPosRight.X].TurnCount = 0;
                _chessBoard[endPosRight.Y, endPosRight.X].IsEnd = true;
                return;
            }

            if (fs1 == true)
            {
                _chessBoard[startPosLeft.Y, startPosLeft.X].Status = BlockStatus.StartGot;
                _chessBoard[startPosLeft.Y, startPosLeft.X].TurnCount = 0;
                _chessBoard[startPosLeft.Y, startPosLeft.X].IsStart = true;
            }
            if (fs2 == true)
            {
                _chessBoard[startPosRight.Y, startPosRight.X].Status = BlockStatus.StartGot;
                _chessBoard[startPosRight.Y, startPosRight.X].TurnCount = 0;
                _chessBoard[startPosRight.Y, startPosRight.X].IsStart = true;
            }
            if (fe1 == true)
            {
                _chessBoard[endPosLeft.Y, endPosLeft.X].IsEnd = true;
                _chessBoard[endPosLeft.Y, endPosLeft.X].TurnCount = 0;
                _chessBoard[endPosLeft.Y, endPosLeft.X].Status = BlockStatus.EndGot;
            }
            if (fe2 == true)
            {
                _chessBoard[endPosRight.Y, endPosRight.X].IsEnd = true;
                _chessBoard[endPosRight.Y, endPosRight.X].TurnCount = 0;
                _chessBoard[endPosRight.Y, endPosRight.X].Status = BlockStatus.EndGot;
            }
            #endregion
        }
        /// <summary>
        /// Get Path
        /// </summary>
        /// <returns></returns>
        public BoardPoint[] GetPath()
        {
            bool flag = true;

            int stepCount = 0;
            while (flag)
            {
                flag = false;

                for (int y = _yStart; y < _rowCount; ++y)
                    for (int x = 0; x < _colCount; ++x)
                    {
                        if (_chessBoard[y,x].TurnCount == stepCount)
                        {
                            int[] xArray = {0, 0, 1, -1};
                            int[] yArray = {-1, 1, 0, 0};
                            foreach(Direction dir in Enum.GetValues(typeof(Direction)))
                            {
                                int tmpX = xArray[(int)dir], tmpY = yArray[(int)dir];
                                
                                for (int i = 1; x + tmpX * i >= 0 && x + tmpX * i < _colCount
                                    && y + tmpY * i >= 0 && y + tmpY * i < _rowCount; ++i)
                                {
                                    int internalTmpX = x + tmpX * i;
                                    int internalTmpY = y + tmpY * i;

                                    //int len = Math.Abs(y - internalTmpY) + Math.Abs(x - internalTmpX);
                                    //if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.StartCurrent
                                    //    && _chessBoard[internalTmpY, internalTmpX].TurnCount == stepCount + 1
                                    //    && _chessBoard[internalTmpY, internalTmpX].StepCount > _chessBoard[y, x].StepCount + len)
                                    //{
                                    //    _chessBoard[internalTmpY, internalTmpX].StepCount = 
                                    //}
                                    if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.New)
                                    {
                                        _chessBoard[internalTmpY, internalTmpX].Status = _chessBoard[y, x].Status;
                                        _chessBoard[internalTmpY, internalTmpX].PrevBlock = _chessBoard[y, x];
                                        _chessBoard[internalTmpY, internalTmpX].TurnCount = stepCount + 1;

                                        flag = true;
                                        continue;
                                    }
                                    if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.EndGot
                                        && _chessBoard[y, x].Status == BlockStatus.StartGot)
                                    {
                                        // get the result
                                        return subGetPath(_chessBoard[y,x], _chessBoard[internalTmpY, internalTmpX]);
                                    }
                                    if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.StartGot
                                        && _chessBoard[y, x].Status == BlockStatus.EndGot)
                                    {
                                        // get the result
                                        return subGetPath(_chessBoard[internalTmpY, internalTmpX], _chessBoard[y, x]);
                                    }

                                    break;
                                }
                            }
                        }
                    }

                for (int y = _yStart -1; y >=0; --y)
                    for (int x = 0; x < _colCount; ++x)
                    {
                        if (_chessBoard[y, x].TurnCount == stepCount)
                        {
                            int[] xArray = { 0, 0, 1, -1 };
                            int[] yArray = { -1, 1, 0, 0 };
                            foreach (Direction dir in Enum.GetValues(typeof(Direction)))
                            {
                                int tmpX = xArray[(int)dir], tmpY = yArray[(int)dir];

                                for (int i = 1; x + tmpX * i >= 0 && x + tmpX * i < _colCount
                                    && y + tmpY * i >= 0 && y + tmpY * i < _rowCount; ++i)
                                {
                                    int internalTmpX = x + tmpX * i;
                                    int internalTmpY = y + tmpY * i;

                                    //int len = Math.Abs(y - internalTmpY) + Math.Abs(x - internalTmpX);
                                    //if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.StartCurrent
                                    //    && _chessBoard[internalTmpY, internalTmpX].TurnCount == stepCount + 1
                                    //    && _chessBoard[internalTmpY, internalTmpX].StepCount > _chessBoard[y, x].StepCount + len)
                                    //{
                                    //    _chessBoard[internalTmpY, internalTmpX].StepCount = 
                                    //}
                                    if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.New)
                                    {
                                        _chessBoard[internalTmpY, internalTmpX].Status = _chessBoard[y, x].Status;
                                        _chessBoard[internalTmpY, internalTmpX].PrevBlock = _chessBoard[y, x];
                                        _chessBoard[internalTmpY, internalTmpX].TurnCount = stepCount + 1;

                                        flag = true;
                                        continue;
                                    }
                                    if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.EndGot
                                        && _chessBoard[y, x].Status == BlockStatus.StartGot)
                                    {
                                        // get the result
                                        return subGetPath(_chessBoard[y, x], _chessBoard[internalTmpY, internalTmpX]);
                                    }
                                    if (_chessBoard[internalTmpY, internalTmpX].Status == BlockStatus.StartGot
                                        && _chessBoard[y, x].Status == BlockStatus.EndGot)
                                    {
                                        // get the result
                                        return subGetPath(_chessBoard[internalTmpY, internalTmpX], _chessBoard[y, x]);
                                    }

                                    break;
                                }
                            }
                        }
                    }

                stepCount++; 
            }

            return null;

        }

        /// <summary>
        /// get path
        /// </summary>
        /// <returns></returns>
        private BoardPoint[] subGetPath(BoardBlock startCurBlock, BoardBlock endCurBlock)
        {
            BoardPoint[] startlist = getPath(startCurBlock);
            BoardPoint[] endList = getPath(endCurBlock);

            List<BoardPoint> list = new List<BoardPoint>();
            for (int i = startlist.Length - 1; i >= 0; i--)
            {
                list.Add(startlist[i]);
            }
            list.AddRange(endList);
            return list.ToArray<BoardPoint>();
        }

        private BoardPoint[] getPath(BoardBlock curBlock)
        {
            List<BoardPoint> list = new List<BoardPoint>();
            for (; curBlock.IsEnd == false && curBlock.IsStart == false
                ; curBlock = curBlock.PrevBlock)
            {
                list.Add(new BoardPoint(curBlock.PositionX, curBlock.PositionY));
            }
            list.Add(new BoardPoint(curBlock.PositionX, curBlock.PositionY));
            return list.ToArray<BoardPoint>();
        }
    }
}
